import java.util.BitSet;

class SimpleHash{
    public int cap; // 当前容量
    public int seed;//随机值

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }
    public int hash(String key) {
        int h;
        return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
}
public class MyBloomFileter {
    public BitSet bitSet;
    public int usedSize;
    public static final int DEFAULT_SIZE = 1 << 100;
    int[] seeds = {11,33,55,99,88,46};
    SimpleHash[] simpleHashes;

    public MyBloomFileter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[seeds.length];
        for(int i = 0; i < simpleHashes.length;i++) {
            simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);
        }
    }
    public void add(String val) {
        for(SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            bitSet.set(index);
        }
        usedSize++;
    }
    public boolean contains(String val) {
        for (SimpleHash simpleHash :simpleHashes) {
            int index = simpleHash.hash(val);
            if(!bitSet.get(index)) {
                return false;
            }
        }
        return true;
    }

}
